package com.zklh.leetcode.structure.lfu;

import java.util.*;

/**
 * @author ：tong nan
 * @date ：Created in 2021/6/17 10:41
 * @description ：Least frequently used 最不经常使用
 *
 * 思路 : 刚开始思路是 两个数据结构
 * @modifiedBy ：
 */
public class LFUCache {
    private Map<Integer, Integer> keyToValue;
    private Map<Integer, Integer> keyToFreq;
    private Map<Integer, LinkedHashSet<Integer>> freqToKeys;
    private int capacity;
    private int minFreq = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        keyToValue = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
    }

    public void put(int key, int val) {
        if (!keyToValue.containsKey(key)) {
            addNew(key, val);
        } else {
            keyToValue.put(key,val);
            increaseFreq(key);
        }
    }


    public int get(int key) {
        if(keyToValue.containsKey(key)) {
            increaseFreq(key);
            return keyToValue.get(key);
        }
        return -1;
    }

    /**
     * 新增
     * @param key
     * @param val
     */
    private void addNew(int key, int val){

        if (keyToValue.size() == capacity) {
            removeLeastFrequently();
        }

        keyToValue.put(key, val);
        keyToFreq.put(key, 1);
        freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
        freqToKeys.get(1).add(key);
        minFreq = 1;
    }

    /**
     * 增加key访问次数
     * @param key
     */
    private void increaseFreq(int key) {
        // 迁移在fks中的位置
        freqToKeys.putIfAbsent(keyToFreq.get(key)+1, new LinkedHashSet<>());
        freqToKeys.get(keyToFreq.get(key)).remove(key);
        freqToKeys.get(keyToFreq.get(key)+1).add(key);

        // 迁移后修改minFreq
        if (keyToFreq.get(key) == minFreq) {
            if (freqToKeys.get(keyToFreq.get(key)).size() == 0) {
                minFreq++;
            }
        }

        // 修改key访问频次
        keyToFreq.put(key, keyToFreq.get(key)+1);
    }

    /**
     * 移除最少使用 且 最远使用的元素
     */
    private void removeLeastFrequently(){
        int removedNode = freqToKeys.get(minFreq).iterator().next();
        freqToKeys.get(minFreq).remove(removedNode);
        keyToValue.remove(removedNode);
        keyToFreq.remove(removedNode);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<>(freqToKeys.keySet());
        Collections.sort(list);
        for (Integer i : list) {
            Set<Integer> set = freqToKeys.get(i);
            for (Integer i1 : set) {
                sb.append(i1+",");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1,10);
        cache.put(2, 20);

        cache.get(1);

        cache.put(3,30);

        cache.get(2);
    }
}
